每日一问之初识牛顿迭代法（Newton's method）

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 2k | 阅读时长 ≈ 2 分钟

什么是牛顿迭代法？

今天在刷 LeetCode 的 sqrt(x) 这道题的时候，看到别人的解法中有使用牛顿迭代法。之前也看到这个方法很多次，但都没有去了解。今天正好就这个问题来稍微整理一下：

  • 什么是牛顿法？
  • 为什么可以用它来求解开方问题？

什么是牛顿法

在维基百科中的定义如下：

In numerical analysis, Newton’s method (also known as the Newton–Raphson method), named after Isaac Newton and Joseph Raphson, is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function. It is one example of a root-finding algorithm.

牛顿法是一种用于找到实数函数的根的近似值的方法，是求根算法中的一个代表。

一个变量中的 Newton-Raphson 方法实现如下，主要的想法来自这个视频，这个教授讲解的挺明白的，一共有 7 个视频。

假设我们有一个连续的函数，其在 x 轴上存在很多根（零点）。现在在 x 轴上取一初始点 *x1*，该点对应的函数值为 f(x1)。然后在该点的函数值附近画切线，切线与 x 轴的交点为 *x2*。假设 x2 =x1- △x，在该三角形中，可以求得斜率 s =f(x1)/△x，化解可得 △x = f(x1)/s。s 即为函数在 x1 处的导数，所以有△x = f(x1)/f’(x1)，最后代入得 x2= x1 - f(x1)/f’(x1)。后面在 x2 对应的函数值处取切线，然后开始新一轮的迭代。之后再循环这个过程，直到达到足够准确的值。过程中迭代的公式可以写成：$$x_{n+1}=x_n - \frac{f(x_n)}{f’(x_n)}$$

为什么可以用它来求解开方问题？

根据上面的基本介绍，牛顿法是用于求解一个实数函数的根的近似值的方法。然而开方问题可以看成是对方程 x2 - n =0 求根的问题，所以就可以用牛顿法来求解：首先可以得知 f(x) = x2 - n ，f’(x) = 2x，所以迭代公式为:
$$x_{n+1}=x_{n} - \frac{ x_{n}^2 - n}{2x_{n}} = \frac{x_n + \frac{n}{x_n}}{2}$$

依据该迭代公式，对应 LeetCode 的 sqrt(x) 这道题写成 Python 代码就会很简洁，比二分法要简洁多了，且运行时间也快一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """       
        
        """
        # 采用二分法
        low, high = 0, x
        while(low <= high):
            mid = int((low + high) / 2)
            if mid*mid > x :
                high = mid - 1
            elif mid*mid < x:
                low = mid + 1
            else:
                return mid

        
        return low - 1
        """
        # 采用牛顿迭代法
        r = x
        while r*r > x:
            r = int((r + x/r) / 2)
        
        return r

参考

[1]. Newton’s method - wikipedia

[2]. Calculus: Newton’s Method (1 of 7) Basics Continued: Roots of Functions

P.S：文中有错欢迎指出，互相学习。